template<class T>
inline string toBin(T num, int len){
    string result="";
    if(num==T(0)){
        result="0";
    }else{
        while(num>0){
            result = (num&1LL ? "1" : "0") +result ;
            num>>=1;
        }
    }
    while(LN(result)<len){
        result = "0"+result;
    }
    return result;
    
}

//--------------------------------------------------------------------------
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    default_random_engine generator (seed);
    uniform_int_distribution<int> distribution(0,n-1);

    int number = distribution(generator);
//----------------------------------------------------------
inline int encodePos(int rpos, int cpos, int RR, int CC){
        return rpos*CC + cpos ;
}
inline int decodeR(int rpos, int RR, int CC){
        return rpos/CC;
}
inline int decodeC(int cpos, int RR, int CC){
        return cpos%CC;
}
//--------------------------------------------------------------------
//treap codes
//--------------------------------------------------------------------
struct Node {
	int key, priority, size;
	Node* left, *right;
	Node(int k, int p) :
			key(k), priority(p), left(NULL), right(NULL), size(1) {
	}
	Node(int k) :
			key(k), left(NULL), right(NULL), priority(rand()), size(1) {
	}
};
inline int sz(Node *root) {
	if (root == NULL)
		return 0;
	return root->size;
}
inline void upd(Node *root) {
	if (root != NULL) {
		root->size = 1 + sz(root->left) + sz(root->right);
	}
	return ;
}
Node* search(Node *root, int key) {
	if (root == NULL)
		return NULL;
	if (key < root->key)
		return search(root->left, key);
	if (key > root->key)
		return search(root->right, key);
	return root;
}
Node* rotRight(Node *root) {
	Node* pivot = root->left;
	root->left = pivot->right;
	pivot->right = root;
	upd(root->right),upd(root);
	return pivot;
}

Node* rotLeft(Node *root) {
	Node* pivot = root->right;
	root->right = pivot->left;
	pivot->left = root;
	upd(root->left),upd(root);
	return pivot;
}
Node* insert(Node *root, Node *novo) {
	if (root == NULL)
		return novo;
	if (root->key < novo->key) {
		root->right = insert(root->right, novo);
		if (root->right->priority > root->priority)
			root = rotLeft(root);
	} else {
		root->left = insert(root->left, novo);
		if (root->left->priority > root->priority)
			root = rotRight(root);
	}
	upd(root);
	return root;
}

Node* erase(Node* root, int key) {
	if (root == NULL) {
		return root;
	}
	if (root->key < key)
		root->right = erase(root->right, key);
	else if (root->key > key)
		root->left = erase(root->left, key);
	else {
		if (root->left != NULL) {
			if (root->right != NULL) {
				if (root->left->priority < root->right->priority) {
					root = rotLeft(root);
					root->left = erase(root->left, key);
				} else {
					root = rotRight(root);
					root->right = erase(root->right, key);
				}
			} else {
				Node* aux = root->left;
				delete root;
				return aux;
			}
		} else {
			if (root->right != NULL) {
				Node* aux = root->right;
				delete root;
				return aux;
			} else {
				delete root;
				return NULL;
			}
		}
	}
	upd(root);
	return root;
}
Node * Find_kth_Node(Node *root, int k) {
	if (sz(root) < k)
		return NULL;
	int ans = 1 + sz(root->left);
	if (ans == k)
		return root;
	if (ans < k)
		return Find_kth_Node(root->right, k - ans);
	return Find_kth_Node(root->left, k);
}
int count_less(Node *root, int k) {
	if (root == NULL)
		return 0;
	if(root->key<k){
		return 1+sz(root->left)+ count_less(root->right,k);
	}
	return count_less(root->left,k);
}
Node* clear(Node* root) {
	if (root != NULL) {
		clear(root->left);
		clear(root->right);
		delete root;
	}
}

void Traverse(Node *root, int level) {
	if (root == NULL)
		return;
	printf("[%d = > %d,%d,%d]->\n", level, root->key, root->priority,
			root->size);
	Traverse(root->left, level + 1);
	Traverse(root->right, level + 1);
}
//----------------------------------------------------------------------
const double pii = (double)(2.)*acos(0);

struct Rect {
    int x1,x2,y1,y2;
    Rect(int x1_=0, int x2_=0, int y1_=0,int y2_=0):
        x1(x1_),x2(x2_),y1(y1_),y2(y2_) {
        ;
    }
    void Format() {
        if(this->x1>this->x2)swap(this->x1,this->x2);
        if(this->y1>this->y2)swap(this->y1,this->y2);
    }
 
};
int Area(Rect A) {
    return ((A.x2-A.x1)) * ( (A.y2-A.y1) );
}
Rect Intersection(Rect A, Rect B) {
    if( A.y2<B.y1 || A .y1>B.y2 || A.x2 < B.x1 || A.x1 > B.x2) {
        return Rect(0,0,0,0);
    }
 
    flag=true;
    return Rect( max(A.x1,B.x1), min(A.x2,B.x2),
                 max(A.y1,B.y1), min(A.y2,B.y2)
               );
}
//------------------------------------------------------------------------
template<class T>
inline T fastIn() {
    register char c=0;
    register T a=0;
    bool neg=false;
    while(c<33)c=getchar();
    while(c>33) {
        if(c=='-') {
            neg=true;
        } else {
            a= (a*10)+(c-'0');
        }
        c=getchar();
    }
    return neg?-a:a;
}
//----------------------------------------------------------------------
//split a string
vector<string> parse(string mystr){
    char *sentence = (char*)mystr.c_str(); // string to chat array
    char *word;
    static char delim[]=" ";
    vector<string> words;
    for(word=strtok(sentence,delim);word; word=strtok(0,delim)){
        if( strlen(word) )
            words.pb(word);
    }
    return words;
}
---------------------------------------------
---------------------------------------------

Number Library :
inline bool int_overflow(int a , int b, string com){
    long long max_value = (1LL<<31)-1;
    if(com=="add"){
        return ( a > (max_value-b) ) ;
    }
    else{
        assert(b!=0);
        return ( a > (max_value/b) );
    }
}
inline bool long_overflow(long long a , long long b, string com){
    unsigned long long max_value = (1ULL<<63)-1;
    if(com=="plus"){
        return ( a > (max_value-b) ) ;
    }
    else{
        assert(b!=0);
        return ( a > (max_value/b) );
    }
}
//check if a number is exact power of 2
inline bool pTwo(unsigned long long x) {
    return (x != 0) && ((x & (x - 1)) == 0);
}

template< class T >
inline T two( T var ){
    return var*var ;
}
inline Int fastPow(Int x, Int y) {
    Int res= (Int)1;
    for ( ; y ; ) {
        if ( (y&1) ) {
            res*= x;
        }
        x*=x;
        y>>=1;
    }
    return res;
}
//fast power with mod
const Int mod = 1000000007LL;
inline Int domod(Int x){
  if(x<0)x+=mod;
  return x%mod;
}
inline Int fastPow(Int a, Int b) {
    Int x= (Int)1,y= domod(a);

    while (b>0) {
        if (b&1) {
            x= domod(x*y);
        }
        y=domod(y*y);
        b>>=1;
    }
    return domod(x);
}

template< class T1, class T2 >
inline T2 MOD( T1 x , T2 b ){
    return (x%b);
}
template< class T >
inline T gcd(T a, T b){
    // NEGATIVE VALUE'R GCD HOTE PARBE NA
    assert( (a >=0 && b>=0 ) );
    while( b > T(0) ){
        a%=b;
        swap(a,b);
    }
return a;
}

inline int toI(string _str){
    // STRING EMPTY HOTE PARBE NA
    assert( LN(_str) );
    int var;
    sscanf(_str.c_str(),"%d",&var);
return var;
}
inline string toS(int var){
    char _buff[50];
    sprintf( _buff,"%d",var);
return (string)_buff;
}


struct Triple {
    Int d;
    Int x;
    Int y;
    Triple(Int d, Int x, Int y):
            d(d),x(x),y(y) {
        ;
    }
};
Triple egcd(Int a, Int b) {
    if (!b)return Triple(a,1,0);
    Triple q=egcd(b,a%b);
    return Triple(q.d, q.y, q.x-a/b*q.y);
}
inline Int invmod(Int a, Int n) {
    Triple t=egcd(a,n);
    if (t.d>1)return 0;
    Int r=t.x%n;
    return (r<0?r+n:r);
}
const int mod=(int)1e9+7;
const int maxn=1010;
Int im[maxn]; //inverse mod
Int fact[maxn];
inline void findFactorials(int upto) {
    fact[0]=fact[1]=im[1]=1;
    for (int i=2;i<=upto;++i) {
        im[i]=invmod(i,mod);
        fact[i]=(fact[i-1]*i)%mod;
    }
}
Int C[maxn][maxn];
// find NcR
Int ncr(Int a, Int b) {
    int LM=min(b,a-b);
    if (C[a][LM])return C[a][LM];
    C[a][0]=1LL;
    int LIM=(a+3)>>1;
    for (int U=a,D=1; D<LIM; ++D,--U) {
        C[a][D]=(((C[a][D-1] * U)%mod) * im[D])% mod;
    }
    return C[a][LM];
}
// another NcR formula
Int ncr(Int n, Int r){
    return ( (fact[n]*(invmod(fact[r],mod)%mod))%mod * invmod(fact[n-r],mod)%mod ) %mod;
}

inline void preprocess() {
    findFactorials(1000);
    SET(C,0);
}

Int fib[maxn+5];
inline void Fibonacci(int upto) {
    fib[0]=0;
    fib[1]=1;
    fib[2]=1;
    for (int i=3;i<=upto;++i) {
        fib[i]=fib[i-1]+fib[i-2];
    }
}

/*
 * http://goo.gl/8tUaQ
 * Zeckendorf(n)= {
 * local(k); a=0;
 * while(n>0, k=0;
 * 	while(fibonacci(k)<=n, k=k+1);
 * 	a=a+10^(k-3); n=n-fibonacci(k-1); ); a
 * }
 *
 * { for (n=0, 10000, Zeckendorf(n); print(n, " ", a);
 */

int res[50];
int leftmost;
inline void Zeckendorf(int n) {
    int k;
    SET(res,0);

    leftmost=-1;
    while (n>0) {
        k=0;
        while (fib[k]<=n) {
            k=k+1;
        }
        res[k-3]=1;
        n=n-fib[k-1];
        if (leftmost==-1)leftmost=k-3;
    }
    for (int i=leftmost;i>=0;--i)
        putchar(res[i]?'1':'0');
    line;

}
int tot;
vector< pair<Int,int> > primeDivisors;
inline void factorize(Int number) {
    primeDivisors.clear();
    for (int i=0; i<cnt&&primes[i]*primes[i]<=number;++i) {
        if ( (number%primes[i]) ==0) {
            int power=0;
            while ((number%primes[i])==0) {
                number/=primes[i];
                ++power;
            }
            primeDivisors.pb(mk(primes[i],power));
        }
    }
    if ( number!=1) {
        primeDivisors.pb(mk(number,1));
    }
    tot=SZ(primeDivisors);
}

vector< pair<Int,int> >primeDivisors;
inline void factorize(Int number) {
    primeDivisors.clear();
    for (Int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            int power = 0;
            do {
                power++;
                number /= i;
            } while (number % i == 0);
            primeDivisors.pb(mk(i, power));
        }
    }
    if (number != 1)
        primeDivisors.pb(mk(number, 1));
}
vector<int> divisors;
void genDivisor(int at, int current) {
    if (at==SZ(primeDivisors)) {
        divisors.pb(current);
        return ;
    }
    int p=primeDivisors[at].first;
    int power=primeDivisors[at].second;
    for (int i=0;i<=power;++i) {
        genDivisor(at+1,current);
        current*=p;
    }
}
inline void getDivisor(int N) {
    factorize(N);
    divisors.clear();
    genDivisor(0,1);
    cout<<N<<" = ";
    fo(i,SZ(divisors)){
      cout<<divisors[i]<<' ';
    }
    line;
}

const int inf = (int)100000;
bitset<inf> used;
int primes[inf];
int cnt;

inline void sieve() {
    int sqrtN = (int)sqrt((double)inf)+1;
    used=0;
    int i,j;
    for (i=3;i<=sqrtN;i+=2) {
        if (!used[i]) {
            for (j=i*i;j<inf;j+=i) {
                used[j]=1;
            }
        }
    }
    cnt=0;
    primes[cnt++]=2;
    for (i=3;i<inf;i+=2) {
        if (!used[i])primes[cnt++]=i;
    }
}
inline Int getNext(int num, int prime) {
    Int v=ceil( ((double)num)/prime );
    v=v*prime;
    if (v==prime)v+=prime;
    return v;
}
inline void segmentSieve(int a, int b) {
    used=0;
    int i;
    int upto= (int)sqrt(double(b))+1;
    for (i=0; i<cnt&&primes[i]<=upto;++i) {
        for (Int j=getNext(a,primes[i]);j<=b;j+=primes[i]) {
            used[j-a]=1;
        }
    }
    int cnt=0;
    for (Int i=lo;i<=hi;++i) {
        if (i!=1&&!used[ (int)i-lo]) {
            ++cnt;
        }
    }
    cout<<cnt;
}
//-------------------------------------------
// return number of divisors of a number "num"
// need sieve() function to call first

inline Int Divisors(Int num) {
    Int res=1;
    for (Int i=0; i<cnt&&(primes[i]*primes[i])<=num; ++i) {
        if ( num%primes[i] ==0 ) {
            int power=0;
            do {
                num/=primes[i];
                ++power;
            } while (num%primes[i] ==0 );
            res*=(power+1);
        }
    }
    if (num!=1) {
        res*=(2);
    }
    return res;
}
// return number of divisors of a number "num^3"
inline Int Divisors_3(Int num) {
    Int res=1;
    for (Int i=2; i*i<=num; ++i) {
        if ( (num%i) ==0 ) {
            int power=0;
            do {
                num/=i;
                ++power;
            } while (num%i ==0 );
            res*=  ( (power*3) +1 )  ;
        }
    }
    if (num!=1) {
        res*=( 4 ) ;
    }
    return res;
}
//---------------------------------------

// number of tailing zero = min( number of 2, number of 5 )
//----------------------------------------------
//calculate
//number of 2, and 5  n!
inline Int calc(int n,int x) {
    Int ret=0;
    for ( Int i=1; i<=n; i*=x ) {
        Int var = (Int)(n/i);
        if (var<0)break;
        ret+=var;
    }
    return ret;
}

//calculate
//number of 2, and 5 in p^q
inline Int calc(int p,int q, int x) {
    //factorize p respect to x;
    Int ret=0;

    while ( (p%x)==0 ) {
        p/=x;
        ++ret;
    }
    return ret*q;
}
//----------------------------------------------
  
const double gammaa = 0.5772156649;
const double Bn[] = {1.0/6.0, -1.0/30.0, 1.0/42.0, -1.0/30.0, 5.0/66.0};
//calculates n-th Harmonic number
//Hn = 1 + 1/2 + 1/3 + ..... + 1/n
inline double Hn(int n) {
    if (n <= 0) return 0;
    double r = 0;
    int i;
    if (n <= 1000) {
        for (i = 1; i <= n; i++) {
            r += (1.0/(double)i);
        }
        return r;
    }
    r = log(n) + gammaa + .5/n;
    for (i = 0; i < 5; i++) {
        r -= (Bn[i] / (2.0*(i+1)*pow(n,2*(i+1)))) ;
    }
    return r;
}

//how many number divisible in range given yeara <= yearb
public long Calculate(long yeara, long yearb, int div) {
        long a = (long) Math.ceil(((double) yeara) / div) * div;
        long b = (long) Math.floor(((double) yearb) / div) * div;
        //debug(yeara+"_"+yearb+"_"+div);
        if (a > b) {
            return 0;
        }
        return ((b - a) / div) + 1;
}

------------------------------------------
------------------------------------------

//A 2-D BIT example.

const int maxn=1002;
int Tree[maxn][maxn];
bool Present[maxn][maxn];

inline void Update(int x, int y, int delta) {
    int y2 = y;
    while (x <= maxn) {
        y = y2;
        while ( y <= maxn ) {
            Tree[x][y] += delta;
            y +=(y & -y);
        }
        x += (x & -x);
    }
}

inline int Query(int x, int y) {
    int y2 = y;
    int ret = 0;
    while (x > 0) {
        y = y2;
        while ( y > 0 ) {
            ret += Tree[x][y];
            y -= (y & -y);
        }
        x -= (x & -x);
    }
    return ret;
}

inline void Solve() {
    SET(Tree,0);
    SET(Present,false);
    int q,sign;
    int x,y;
    int x1,y1,x2,y2;
    CI(q);
    while (q) {
        CI(sign);
        if (!sign) {
            CI(x,y);
            ++x;
            ++y;
            //update this point
            //if already not present
            if (Present[x][y]==false) {
                Present[x][y]=true;
                Update(x,y,1);
            }
        }
        else {
            CI(x1,y1,x2,y2);
            ++x1;
            ++y1;
            ++x2;
            ++y2;
            int total =Query(x2, y2) - Query(x1-1, y2) - Query(x2, y1-1) + Query(x1-1 ,y1-1);
            cout<<total;
            line;
        }
        --q;
    }
}
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
        cout<<"Case "<<i<<":\n";
        Solve();
    }
    return 0;
}    

---------------------------------------
---------------------------------------
// A DP Problem example
class BaseConfusion {
public:
    long long sum(int M, int N, int B);
};
vector< int > vi;
int base;
inline void parse( int var ) {
    vi.clear();
    while ( var > 0 ) {
        vi.pb( var %base );
        var/=base;
    }
    return ;
}

inline Int power( int indx , int BASE) {
    Int res=1LL;
    for (int i=0;i<indx;++i) {
        res*=BASE;
    }
    return res;
}
pair<Int,Int> dp[66][2];
int vis[66][2];
inline pair<Int,Int> go( int indx, int smaller ) {
    if ( indx==-1 ) {
        return mk( 0,1 );
    }
    if ( vis[indx][smaller]!=-1 ) {
        return dp[ indx ][smaller];
    }
    vis[indx][smaller]=1;

    int to = smaller==0 ? vi[ indx ] : base-1 ;
    pair<Int,Int> RET = mk(0,0);

    for (int d=0;d<=to;++d) {
        int nxtsmaller = smaller|( d < vi[indx] ? 1 : 0 );
        pair<Int,Int> v = go( indx-1, nxtsmaller );
        RET.f+= ( v.f+ ( power(indx, base+1 )*d*v.s) ) ;
        RET.s+= v.s;
    }
    return dp[ indx][smaller] = RET;
}
inline Int doit( int N ) {
    if ( N==0 )return 0;
    SET(vis,-1);
    parse( N );
    return go( SZ(vi)-1, 0 ).f;
}
long long BaseConfusion :: sum(int M, int N, int B) {
    base = B;
    Int res = doit( N ) - doit( M-1 );
    return res;

}

---------------------------------------
---------------------------------------
// BIT and rectangle
// max number inside rectanlges
const int SIZE = 512;
int a[SIZE][SIZE];
int mx[SIZE<<1][SIZE<<1];
int n,m,q;

inline void Add(int x,int y,int v) {
    int a = x+n-1;
    int b = y+m-1;

    mx[a][b]=v;
    for (int j = (b - 1) >> 1; j >= 0; --j >>= 1) {
        mx[a][j] = max(mx[a][(j << 1) | 1], mx[a][(j + 1) << 1]);
    }

    for (int i = (a - 1) >> 1; i >= 0; --i >>= 1) {
        for (int j = b; j >= 0; --j >>= 1) {
            mx[i][j] = max(mx[(i << 1) | 1][j], mx[(i + 1) << 1][j]);
        }
    }
}
inline int MaxY(int i, int x1, int x2) {
    int a, b, t;
    int lmax = mx[i][a = x1 + m - 1], rmax = mx[i][b = x2 + m - 1];
    for (int l = a, r = b; l < r - 1; --l >>= 1, --r >>= 1) {
        if ((l & 1)&& lmax < mx[i][t = l + 1]) lmax = mx[i][t];
        if (!(r & 1) && rmax < mx[i][t = r - 1]) rmax = mx[i][t];
    }
    return max(lmax, rmax);
}
inline int Max(int x1, int y1, int x2, int y2) {
    int a, b, t;
    int lmax = MaxY(a = x1 + n - 1, y1, y2), rmax = MaxY(b = x2 + n - 1, y1, y2);
    for (int lx = a, rx = b; lx < rx - 1; --lx >>= 1, --rx >>= 1) {
        if ((lx & 1) && lmax < (t = MaxY(lx + 1, y1, y2))) lmax = t;
        if (!(rx & 1) && rmax < (t = MaxY(rx - 1, y1, y2))) rmax = t;
    }
    return max(lmax, rmax);
}


inline void Proc() {
    int R;
    CI(R,q);
    m=n=R;
    int am = m, an = n;
    n--, m--;
    while (n & (n + 1)) {
        n |= n + 1;
    }
    n++;
    while (m & (m + 1)) {
        m |= m + 1;
    }
    m++;

    for (int i = 0; i < am; i++) {
        for (int j = 0; j < an; j++) {
            CI(a[i][j]);
            Add(i, j, a[i][j]);
        }
    }
    int r1,c1,r2,c2;
    int S;
    line;
    while (q--) {
        CI(r1,c1,S);
        r2=r1+S-1;
        c2=c1+S-1;
        cout<<Max(--r1,--c1,--r2,--c2);
        line;
    }
}
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
        cout<<"Case "<<i<<":";
        Proc();
    }
    return 0;
}


--------------------------------------
--------------------------------------
// example of hash kore then BIT
class Interval {
public:
    int s;
    int t;
    Interval(int s=0,int t=0):
            s(s),t(t) {
        ;
    }
};
const int mx = (50005);
int N,Q;
Interval intervals[mx];
int queries[mx];


class MyHash {
#define MAX_HAS_LEN (50005*3) //change accordingly
#define S int //type of points
public :
    map<S,int> mp;
    int points[MAX_HAS_LEN];
    int nPoints;
    int ID;
    inline void clearHash() {
        ID=1;
        mp.clear();
        memset(points,0,sizeof(points));
        nPoints=0;
    }
    inline void Push(int point) {
        points[nPoints]=point;
        ++nPoints;
    }
    inline void Encode() {
        sort(points,points+nPoints,less<int>());
        int prv=INT_MIN;
        for (int i=0;i<nPoints;++i) {
            if (prv!=points[i]) {
                prv=points[i];

                mp[ points[i] ]=ID;
                ++ID;
            }
        }
    }
    inline int GetId(int point) {
        return mp[point];
    }

};
class BIT {
//********************************
//REMEMBER 1[ONE] BASED INDEXING//
//********************************
#define MAX_BIT (50005*3) //change accordingly
public :
    int Tree[MAX_BIT];
    void clearBIT() {
        SET(Tree,0);
    }
    void Update(int idx,int delta) {
        if (idx<=0)return ;

        while (idx<MAX_BIT) {
            Tree[idx]+=delta;
            idx+=(idx & -idx );
        }
    }
    int Query(int idx) {
        if (idx<=0)return 0;

        int ret=0;
        while (idx>0) {
            ret+=Tree[idx];
            idx-=(idx & -idx );
        }
        return ret;
    }
};


inline void Read() {

    CI(N,Q);
    int a,b;
    fo(i,N) {
        CI(a,b);
        intervals[i].s=a;
        intervals[i].t=b;
    }
    fo(i,Q) {
        CI(a);
        queries[i]=a;
    }
}
MyHash hash;
BIT myBit;
inline void Proc() {
    hash.clearHash();
    myBit.clearBIT();
    //for all intervals
    fo(i,N) {
        hash.Push(intervals[i].s);
        hash.Push(intervals[i].t);
    }
    //for all query points
    fo(i,Q) {
        hash.Push(queries[i]);
    }

    hash.Encode();
    //run bit on all encoded intervals
    fo(i,N) {
        int a = hash.GetId( intervals[i].s );
        int b = hash.GetId( intervals[i].t );
        myBit.Update(a,1);
        myBit.Update(b+1,-1);
    }
    
    line;
    //answer the queries
    fo(i,Q) {
        int a=hash.GetId(queries[i]);
        cout<< myBit.Query(a);
        line;
    }

}
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
        cout<<"Case "<<i<<":";
        Read();
        Proc();
    }
    return 0;
}

-------------------------------------
-------------------------------------


// number of points inside rectangles BIT exmple
const int maxn=1002;
int Tree[maxn][maxn];
bool Present[maxn][maxn];

inline void Update(int x, int y, int delta) {
    int y2 = y;
    while (x <= maxn) {
        y = y2;
        while ( y <= maxn ) {
            Tree[x][y] += delta;
            y +=(y & -y);
        }
        x += (x & -x);
    }
}

inline int Query(int x, int y) {
    int y2 = y;
    int ret = 0;
    while (x > 0) {
        y = y2;
        while ( y > 0 ) {
            ret += Tree[x][y];
            y -= (y & -y);
        }
        x -= (x & -x);
    }
    return ret;
}

inline void Solve() {
    SET(Tree,0);
    SET(Present,false);
    int q,sign;
    int x,y;
    int x1,y1,x2,y2;
    CI(q);
    while (q) {
        CI(sign);
        if (!sign) {
            CI(x,y);
            ++x;
            ++y;
            //update this point
            //if already not present
            if (Present[x][y]==false) {
                Present[x][y]=true;
                Update(x,y,1);
            }
        }
        else {
            CI(x1,y1,x2,y2);
            ++x1;
            ++y1;
            ++x2;
            ++y2;
            int total =Query(x2, y2) - Query(x1-1, y2) - Query(x2, y1-1) + Query(x1-1 ,y1-1);
            cout<<total;
            line;
        }
        --q;
    }
}
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
        cout<<"Case "<<i<<":\n";
        Solve();
    }
    return 0;
}
--------------------------------------
--------------------------------------
//Directed MST
import java.io.*;
import java.awt.*;
import java.text.*;
import java.math.*;
import java.util.*;
import java.lang.*;

public class Main implements Runnable {

    final String filename = "in";

    public static void main(String[] args) {
        // new Thread(new Main()).start();
        new Thread(null, new Main(), "1", 1 << 25).start();

    }

    public void run() {
        try {
            //in = new BufferedReader(new InputStreamReader(System.in));
            out = new BufferedWriter(new OutputStreamWriter(System.out));
            in = new BufferedReader(new FileReader(filename + ".in"));
            // out = new BufferedWriter(new FileWriter(filename+".out"));
            int kase = iread();
            for (int i = 1; i <= kase; ++i) {
                //TODO CODE HERE
                solve(i);
            }
            out.flush();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
    Node[] Edges;
    public void solve(int kaseno) throws Exception {
        out.write("Case " + kaseno + ": ");
        int N = iread();
        int E = iread();
        int root = iread();
        Edges = new Node[E];
        int u,v,cost;
        for (int i = 0; i < E; ++i) {
            u = iread();
            v = iread();
            cost = iread();
            Edges[i] = new Node(u,v,cost);
        }
        DirectedMST solve = new DirectedMST(N, E, Edges);
        int ret = solve.Run(root);
        
        out.write( (ret==-1 ? "impossible" : ret )+"\n");
        
    }   

    class DirectedMST {

        final int inf = 1023456789;
        int N;//number of nodes
        int E; // number of edges;
        Node[] edges;
        int[] pre;
        int[] ID;
        int[] vis;
        int[] In;

        DirectedMST(int N, int E, Node[] edges) {
            this.N = N;
            this.E = E;
            this.edges = edges;
            this.pre = new int[N];
            this.ID = new int[N];
            this.vis = new int[N];
            this.In = new int[N];
        }
        public int Run(int root) {
            int ret = 0;
            while (true) {

                //1 :
                for (int i = 0; i < N; ++i) {
                    In[i] = inf;
                }
                for (int i = 0; i < E; ++i) {
                    int u = edges[i].u;
                    int v = edges[i].v;
                    int cost = edges[i].cost;
                    if (cost < In[v] && u != v) {
                        pre[v] = u;
                        In[v] = cost;
                    }
                }
                //If not connected ?
                for (int i = 0; i < N; ++i) {
                    if (i == root) {
                        continue;
                    }
                    if (In[i] == inf) {
                        return -1; // as impossible
                    }
                }

                //2 :
                int cntNode = 0;
                Arrays.fill(ID, -1);
                Arrays.fill(vis, -1);
                In[root] = 0;

                for (int i = 0; i < N; ++i) {
                    ret += In[i];
                    int v = i;
                    while (vis[v] != i && ID[v] == -1 && v != root) {
                        vis[v] = i;
                        v = pre[v];
                    }
                    if (v != root && ID[v] == -1) {
                        for (int u = pre[v]; u != v; u = pre[u]) {
                            ID[u] = cntNode;
                        }
                        ID[v] = cntNode++;
                    }
                }
                if (cntNode == 0) {
                    break;
                }
                for (int i = 0; i < N; ++i) {
                    if (ID[i] == -1) {
                        ID[i] = cntNode++;
                    }
                }

                //3 : 
                for (int i = 0; i < E; ++i) {
                    int u = edges[i].u;
                    int v = edges[i].v;
                    edges[i].u = ID[u];
                    edges[i].v = ID[v];
                    if (edges[i].u != edges[i].v) {
                        edges[i].cost -= In[v];
                    }
                }
                N = cntNode;
                root = ID[root];
            }
            return ret;
        }
    }

    class Node {

        int u;
        int v;
        int cost;

        Node(int u, int v, int cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }
        
        public String toString(){
            return (u+" "+v+" "+cost);
        }
    }

    public void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }

    public int iread() throws Exception {
        return Integer.parseInt(readword());
    }

    public double dread() throws Exception {
        return Double.parseDouble(readword());
    }

    public long lread() throws Exception {
        return Long.parseLong(readword());
    }
    BufferedReader in;
    BufferedWriter out;

    public String readword() throws IOException {
        StringBuilder b = new StringBuilder();
        int c;
        c = in.read();
        while (c >= 0 && c <= ' ') {
            c = in.read();
        }
        if (c < 0) {
            return "";
        }
        while (c > ' ') {
            b.append((char) c);
            c = in.read();
        }
        return b.toString();
    }
}

--------------------------------------
--------------------------------------
// EULAR TOUR AND EULAR PATH PRINT

struct Node {
    int  u;
    int  v;
    string name;
    Node(int u=0,int v=0,string name=""):
            u(u),v(v),name(name) {
        ;
    }
};
int N;
Node  words[1000];
inline void Read() {
    fastRead(&N);
    fo(i,N) {
        words[i].name = fastRead();
        words[i].u = (words[i].name[0]-'a');
        words[i].v = (words[i].name[ LN(words[i].name)-1 ]-'a');
    }
}
int inDegree[27];
int outDegree[27];
int Edges[27][27];
inline void Build() {
    SET(inDegree,0);
    SET(outDegree,0);
    SET(Edges,0);
    fo(i,N) {
        inDegree[ words[i].u ]++;
        outDegree[ words[i].v ]++;
        Edges[ words[i].u ][words[i].v]+=1;
    }
}
inline bool isEular() {
    int cnt=0;
    fo(i,26) {
        int d = abs(inDegree[i]-outDegree[i]);
        if (d==0)continue;
        if (d>1)return false;
        if (d==1)cnt++;
    }
    return cnt<=2 ;
}
bool visited[27];
inline bool isConnected() {
    int u=0;
    fo(i,26) {
        if ( !inDegree[i] && !outDegree[i] )continue;

        if ( inDegree[i]>=outDegree[i] ) {
            u=i;
            if ( inDegree[i]>outDegree[i])break;
        }
    }
    SET(visited,false);
    stack<int> s;
    s.push(u);
    visited[u]=true;
    while (!s.empty()) {
        int f = s.top();
        s.pop();
        fo(i,26) {
            int c = i;
            if ( Edges[f][c]>0 && !visited[c]) {
                visited[c]=true;
                s.push(c);
            }
        }
    }
    fo(i,26) {
        if (inDegree[i] && visited[i]==false)return false;
    }

    return true;
}
bool used[1000];
int path[1000];
void dfs(int now, int &cnt) {
    fo(i,N) {
        if ( words[i].u==now && !used[i]) {
            used[i]=true;
            dfs( words[i].v, cnt);
            path[cnt++]=i;
        }
    }
}
inline void printEular() {
    int u=0;
    fo(i,26) {
        if ( !inDegree[i] && !outDegree[i] )continue;

        if ( inDegree[i]>=outDegree[i] ) {
            u=i;
            if ( inDegree[i]>outDegree[i])break;
        }
    }

    SET(used,false);
    int cnt=0;
    dfs(u,cnt);
    string ret="";
    ret+=words[ path[cnt-1] ].name;
    for (int i=cnt-2;i>=0;--i) {
        ret+=' ';
        ret+=words[ path[i] ].name;
    }
    puts(ret.c_str());

}
inline void Proc() {
    Build();
    if ( isEular()==false || isConnected()==false ) {
        puts("No");
        return ;
    }
    puts("Yes");
    printEular();
}
int main() {
    int tt;
    fastRead(&tt);

    foE(i,1,tt) {
        Read();
        cout<<"Case "<<i<<": ";
        Proc();
    }
    return 0;
}

------------------------------------
------------------------------------

//Another TRI implementation 

#define maxn 500005
#define charset 26
#define maxw 505
vector<int> E[maxn];
int freq[maxw];
char ss[1000010];
char st[maxw];
int hash[maxw];
struct Node {
    int link[charset];
    int fail;
    int f;
    void Set() {
        SET(link,0);
        fail=f=0;
    }
};
Node trie[maxn];
int cnt,root;
inline void Ini_trie() {
    cnt=1;
    root=cnt++;
    trie[0].Set();
    trie[1].Set();
    fo(i,charset) {
        trie[0].link[i]=root;
    }
}
inline void Addinto_trie(char *in,int k) {
    int now=root;
    for(; *in; ++in) {
        int id=*in-'a';
        if(!trie[now].link[id]) {
            trie[cnt].Set();
            trie[now].link[id]=cnt++;
        }
        now=trie[now].link[id];
    }
    hash[k]=now;
}
inline void build() {
    queue<int> q;
    q.push(root);
    while( !q.empty() ) {
        int t=q.front();
        q.pop();
        for(int i=0; i<charset; i++) {
            int tt=trie[t].link[i];
            int ff=trie[t].fail;
            if(trie[t].link[i]) {
                trie[tt].fail=trie[ff].link[i];
                q.push(tt);
            } else {
                trie[t].link[i]=trie[ff].link[i];
            }
        }
    }
}
inline void AC(char *str) {
    int i=0,cur=root;
    for(; str[i]; i++) {
        int id=str[i]-'a';
        cur=trie[cur].link[id];
        trie[cur].f++;
    }
}
void dfs(int u) {
    freq[u]=trie[u].f;
    foit(it,E[u]) {
        int v= (*it);
        dfs(v);
        freq[u]+=freq[v];
    }
}
inline void Solve() {
    int n;
    //{
    Ini_trie();
    for(int i=0; i<maxn; ++i) {
        E[i].clear();
    }
    CI(n);
    getchar();
    gets(ss);
    fo(i,n) {
        gets(st);
        Addinto_trie(st,i);
    }
    //}
    build();
    for(int i=1; i<cnt; ++i) {
        int f = trie[i].fail;
        E[f].pb(i);
    }
    SET(freq,0);
    AC(ss);
    dfs(root);
    fo(i,n) {
        cout<<freq[hash[i]];
        line;
    }

}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in","rt",stdin);
#endif
    int tt;
    CI(tt);
    foE(i,1,tt) {
        cout<<"Case "<<i<<":\n";
        Solve();
    }


    return 0;
}

--------------------------------------
--------------------------------------

// Stable Marriage Problem

enum {
    mx=105
};
struct People {
    int opp;
    int aim;
    vector<int> lst;
    vector<int> priority;
    void Init(int _n) {
        opp=-1;
        aim=0;
        lst.assign(_n,0);
        priority.assign(_n,0);
    }
};
struct Request {
    int opp;
    int own;
};

People man[mx];
People woman[mx];
Request request[mx];
deque<int> q;

inline void Gale_Shapley(int n) {
    q.clear();
    int cnt,m,w;
    for (int i=0;i<n;++i)q.push_back(i);

    while (!q.empty()) {
        cnt=0;
        while (!q.empty()) {
            m=q.front();
            q.pop_front();
            request[cnt].opp=man[m].lst[man[m].aim];
            request[cnt].own=m;
            man[m].aim++;
            cnt++;
        }
        if (cnt==0)break;
        q.clear();
        for (int i=0;i<cnt;++i) {
            m=request[i].own;
            w=request[i].opp;
            if (woman[w].opp==-1||woman[w].priority[m]<woman[w].priority[woman[w].opp]) {
                if (woman[w].opp!=-1) {
                    man[woman[w].opp].opp=-1;
                    q.push_back(woman[w].opp);
                }
                woman[w].opp=m;
                man[m].opp=w;
            }
            else {
                q.push_back(m);
            }
        }

    }
}
int N;
inline void Read() {
    CI(N);

    fo(i,N) {
        man[i].Init(N);
        woman[i].Init(N);
    }

    int tmp;
    for (int i=0;i<N;++i) {
        for (int j=0;j<N;++j) {
            CI(tmp);
            tmp-=N;
            tmp-=1;
            man[i].lst[j]=tmp;
        }
    }
    for (int i=0;i<N;++i) {
        for (int j=0;j<N;++j) {
            CI(tmp);
            tmp-=1;
            woman[i].priority[tmp]=j;
        }
    }
}
inline void Proc() {
    Gale_Shapley(N);
    for (int i=0;i<N;++i) {
        //debug(i+1,man[i].opp+N+1);
        cout<<" ("<<i+1<<' '<<man[i].opp+N+1<<")";
    }
    line;
}
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
        Read();
        cout<<"Case "<<i<<":";
        Proc();
    }
    return 0;
}

----------------------------------------
----------------------------------------

// another DP example
namespace in {
Int a,b;
vector<int> vi;
inline void Read() {
    scanf("%lld %lld",&a,&b);
    if (a>b)swap(a,b);
}
inline void Convert(Int n) {
    vi.clear();
    while (n>0) {
        vi.pb( n%10 );
        n/=10;
    }
    reverse(vi.begin(),vi.end());
}
}

Int dp[20][20][2][2];
//left, right , from, smaller, smaller flag
Int go(int l, int r, int f, int s, int ss) {
    if (l>r) {
        if ( ss==1 )return s==1;
        return 1;
    }
    Int& var=dp[l][r][s][ss];
    if (var!=-1)return var;
    var=0;
    //if already smaller
    if (s==1) {
        for (int d=f;d<=9;++d) {
            var+=go(l+1,r-1,0,1,0);
        }
    }
    else {
        //if left and right is equal
        int u = in::vi[l];
        int v = in::vi[r];
        if ( u==v ) {
            for (int d=f;d<u;++d) {
                //all smaller
                var+=go(l+1,r-1,0,1,0);
            }
            var+=go(l+1,r-1,0, (s|0)  ,ss);
        }
        else if (u>v) {
            for (int d=f;d<u;++d) {
                //all smaller
                var+=go(l+1,r-1,0,1,0 );
            }
            var+=go(l+1,r-1,0,0,1 );
        }
        else {
            for (int d=f;d<u;++d) {
                var+=go(l+1,r-1,0,1,0);
            }
            var+=go(l+1,r-1,0,0,0);
        }
    }
    return var;
}
Int dp2[20][20];
inline Int go2(int i, int j,int from) {
    if (i>j) {
        return 1LL;
    }
    Int &nways=dp2[i][j];
    if (nways!=-1)return nways;
    nways=0;
    for (int d=from;d<=9;++d) {
        nways+= go2(i+1,j-1,0);
    }
    return nways;
}
inline Int Count(Int p) {

    if (p<0)return 0;
    in::Convert(p);
    int l = SZ(in::vi);
    SET(dp,-1);
    Int ret =go(0,l-1,l==1?0:1,0,0);
//     fo(i,l) {
//         cout<<in::vi[i]<<' ';
//     }
//     debug("RESULT ",ret,"");
    for (int i=1;i<l;++i) {
        SET(dp2,-1);
        ret+=go2(0,i-1,i==1?0:1);
    }
    return ret;
}
inline void Solve() {
    in::Read();
    Int x = Count(in::a-1);
    Int y = Count(in::b);
    cout<<y-x;
    line;
}
#define showcase
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
#ifdef showcase
        cout<<"Case "<<i<<": ";
#endif
        Solve();
    }


    return 0;
}


//emax-flow cut
/*
 * E.cxx
 *
 *  Created on: 1:11:47 PM Oct 27, 2012
 *  Author: Pallab
 *
 * "I have not failed, I have just found 10000 ways that won't work.
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait(double seconds) {
	double endtime = clock() + (seconds * CLOCKS_PER_SEC);
	while (clock() < endtime) {
		;
	}
}
#define T int
inline T fastIn() {
	register char c = 0;
	register T a = 0;
	while (c < 33)
		c = getchar();
	while (c > 33) {
		a = (a * 10) + (c - '0');
		c = getchar();
	}
	return a;
}
//emax flow cut
const int INF = 1000 * 1000 * 1000;
struct rib {
	int b, u, c, f;
	int back;
};
inline void add_rib(vector<vector<rib> > & g, int a, int b, int cap, int cost) {
	rib r1 = { b, cap, cost, 0, g[b].size() };
	rib r2 = { a, 0, -cost, 0, g[a].size() };
	g[a].push_back(r1);
	g[b].push_back(r2);
}
inline pair<int, int> min_cost_flow(int k, int n, int s, int t,
		vector<vector<rib> >&g) {
	int flow = 0, cost = 0;
	while (flow < k) {
		vector<int> id(n, 0);
		vector<int> d(n, INF);
		vector<int> q(n);
		vector<int> p(n);
		vector<size_t> p_rib(n);
		int qh = 0, qt = 0;
		q[qt++] = s;
		d[s] = 0;
		while (qh != qt) {
			int v = q[qh++];
			id[v] = 2;
			if (qh == n)
				qh = 0;
			for (int i = 0; i < (int) g[v].size(); ++i) {
				rib & r = g[v][i];
				if (r.f < r.u && d[v] + r.c < d[r.b]) {
					d[r.b] = d[v] + r.c;
					if (id[r.b] == 0) {
						q[qt++] = r.b;
						if (qt == n)
							qt = 0;
					} else if (id[r.b] == 2) {
						if (--qh == -1)
							qh = n - 1;
						q[qh] = r.b;
					}
					id[r.b] = 1;
					p[r.b] = v;
					p_rib[r.b] = i;
				}
			}
		}
		if (d[t] == INF)
			break;
		int addflow = k - flow;
		for (int v = t; v != s; v = p[v]) {
			int pv = p[v];
			size_t pr = p_rib[v];
			addflow = min(addflow, g[pv][pr].u - g[pv][pr].f);
		}
		for (int v = t; v != s; v = p[v]) {
			int pv = p[v];
			size_t pr = p_rib[v], r = g[pv][pr].back;
			g[pv][pr].f += addflow;
			g[v][r].f -= addflow;
			cost += g[pv][pr].c * addflow;
		}
		flow += addflow;
	}
	return pair<int, int>(flow, cost);
}
//-------------
int cnt[26];
const int inf = 1023456789;
inline void count_occurence(string &s) {
	SET(cnt, 0);
	fo(i,LN(s))
		cnt[s[i] - 'a']++;
}
inline void solve() {
	int n;
	string s;
	cin >> s;
	cin >> n;

	vector<string> t(n);
	vector<int> ai(n);
	fo(i,n)
		cin >> t[i] >> ai[i];

	int N = 26+(n*26)+n+2;
	int src = N - 2;
	int snk = N - 1;
	vector<vector<rib> > g(N);

	//-----------------------------
	// add_rib( graph, source, sink, cap, cost )
	count_occurence(s);
	fo(i,26)
		add_rib(g, src, i, cnt[i], 0);
	//-----------------------------
	fo(i,26){
		fo(j,n)
			add_rib(g,i, (26+(j*26)+i) ,inf,j+1);
	}
	fo(j,n){
		count_occurence(t[j]);
		fo(i,26)
			add_rib(g,(26+(j*26)+i), (26*(n+1)+j) ,cnt[i],0);
	}
	fo(j,n)
		add_rib(g,(26*(n+1)+j),snk,ai[j],0);

	pair<int,int> rr = min_cost_flow(LN(s),N,src,snk,g);
	//cout<<rr.first<<' '<<rr.second<<'\n';
	cout<<( rr.first<LN(s) ? -1 : rr.second )<<'\n';
}
int main() {
	int kase = 1;
#if defined( xerxes_pc )
	if (!freopen("E/in1", "r", stdin))
		puts("error opening file E/in "), assert(0);
	kase = 1;
#endif
	fo(i,kase)
	{
		solve();
	}
/*--------------------------------------
		END
----------------------------------------


    
